package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.回溯;

import java.util.*;

/**
 * @author By ZengPeng
 */
public class 力扣_77_组合 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_77_组合().combine(4,2));
        System.out.println(new 力扣_77_组合().combine(1,1));
        System.out.println(new 力扣_77_组合().combine(20,15));
    }

    /**
    题目：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
     你可以按 任何顺序 返回答案。

     示例 1：
     输入：n = 4, k = 2
     输出：
     [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

     示例 2：
     输入：n = 1, k = 1
     输出：[[1]]

    分析：【perfect】
       1.递归 回溯法: 记录开始节点、还需要下潜的深度  . --执行用时：1 ms, 在所有 Java 提交中击败了99.99%的用户
             记得剪枝阿
       优化:
            A :  if (k <= 0 || n < k) 直接返回
            B :  Deque 比 Stack 快？？？
    边界值 & 注意点：
       1.
     **/
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n < k)
            return res;
        Deque<Integer> stack = new ArrayDeque<>();
        recursion(res,1,n,k,stack);
        return res;
    }
    /**
    *  递三要素：1.单步循环【保证循环不变量】 2.返回值  3.终止条件
     * @param  res 结果存储集合
     * @param  start 开始节点
     * @param  n 终止节点
     * @param  k 还剩多少位
     * @param stack 前面保存的值
     **/
    private void recursion(List<List<Integer>> res, int start, int n, int k,Deque<Integer> stack) {
        if(k==stack.size()) {
            res.add(new ArrayList<>(stack));
            return;
        }
        int end = n-k+stack.size()+1;
        for (int i = start; i <= end; i++) {
            stack.push(i);
            recursion(res,i+1,n,k,stack);
            stack.pop();
        }
    }
}
